'''
Created on Nov 19, 2010

@author: James
'''
from game import Directions
import copy

"""
single dot bfs 
 how to use:

  import bfsagent
  
  b = bfsagent.bfsagent()
  
  return b.getActions(problem)
"""


class bfsagent:

    DEBUG_ON = False
    
    # gets the child nodes for parent
    # which are the adjacent tiles
    def getChildren(self,parent):
        to_return = []
        
        x = parent[0]
        y = parent[1]
        
        if x < self.width-1: # node to the right
            if self.nodes[x+1][y]:
                to_return.append([x+1,y])
        if x > 0:
            if self.nodes[x-1][y]: #node to the left
                to_return.append([x-1,y])
        if y < self.height -1:
            if self.nodes[x][y+1]: # node north
                to_return.append([x,y+1])
        if y > 0:
            if self.nodes[x][y-1]: #node south
                to_return.append([x,y-1])
        return to_return

    #translates optimal path into a list of directions            
    def generateActions(self):
        self.actions=[]
        prev_var = []
        for var in self.opt_path:
            if len(prev_var) ==0:
                prev_var = var
            else:
                if var[0] == prev_var[0]:
                    if var[1] > prev_var[1]:
                        self.actions.append(Directions.NORTH)
                    else:
                        self.actions.append(Directions.SOUTH)
                else:
                    if var[0] > prev_var[0]:
                        self.actions.append(Directions.EAST)
                    else:
                        self.actions.append(Directions.WEST)
                prev_var = var            
    
    # recursive bfs
    # finds the goals
    # stops when all paths are longer than the shortest goal path
    def doBFS(self,node,path):
        
        new_path = copy.deepcopy(path) # by val copy of path
                
        #print "doBFS",len(new_path)#,node,new_path
        if node != None:
            
            new_path.append(node)
            
            # do not continue this path if it's longer than the goal path
            if not self.shortest_path_len == 0 and len(new_path) > self.shortest_path_len:
                return
            
            # found a new goal path which is the shortest
            if node[0] == self.food[0] and node[1] == self.food[1]:
                #print "found goal",new_path
                self.opt_path = new_path
                self.shortest_path_len = len(new_path)
                return 
            
            adj_nodes = self.getChildren(node)
            #print "adjacents", adj_nodes
            if adj_nodes != None:
                if len(adj_nodes) > 0:
                    for n in adj_nodes: # we will expand each node
                        if not n in new_path: # only if it's not already in the path
                            self.doBFS(n,new_path)
    # make a matrix of all tiles (called nodes)
    # set each tile that is a wall to false
    def initializeVars(self): 
        self.nodes=[]
        for i in range(0,self.width):
            temp_array=[]
            for j in range(0,self.height):
                if self.walls[i][j]:
                    temp_array.append(False)
                else:
                    temp_array.append(True)
            self.debugPrint( temp_array)
            self.nodes.append(temp_array)
        self.debugPrint("initializeVars: (rows,cols) (" + str(len(self.nodes)) + "," + str(len(self.nodes[0])) + ")")

    def debugPrint(self,str):
        if self.DEBUG_ON:
            print str

    def getActions(self,problem):
        
        self.walls = problem.walls
        self.food = problem.goal
        self.height = self.walls.height
        self.width = self.walls.width
        self.startstate = [problem.getStartState()[0],problem.getStartState()[1]]
        self.shortest_path_len = 0
        self.initializeVars()
        self.opt_path = []
        
        self.debugPrint("getActions: (width,height) (" + str(self.width) + ", " +str(self.height) + ")"  )
        
        self.doBFS(self.startstate, [])
        
        self.debugPrint(self.opt_path)
        
        self.generateActions()
        
        self.debugPrint(self.actions)
        
        return self.actions
    